/***************************************************************************************************
  *Copyright(C),2010-2016,Sumscope
  *FileName	:  pinyin_search_set.cpp
  *Author	:  scofined.qi
  *Version	:  1.0
  *Date		:  2017/11/23
  *Desc		:  //用于主要说明此程序文件完成的主要功能
  *Relation :  
  *Others	:  //其他内容说明
  *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
  *History	:  //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
***************************************************************************************************/
#include "pinyin_search_set.h"
#include "../../allocator/allocator_pool_manager.h"
#include <core/instance/singleton.h>

#ifndef WIN32
#include <sys/mman.h>
#endif

#ifndef BASSERTS
#define BASSERTS //
#endif
#ifndef BASSERT
#define BASSERT //
#endif
#ifndef BLOGERR
#define BLOGERR //
#endif
#ifndef BLOGINFO
#define BLOGINFO //
#endif
#ifndef BLOGDEBUG
#define BLOGDEBUG //
#endif

#ifndef max
#define max(a,b)            ((a) > (b)) ? (a) : (b)
#endif

namespace qb{
	namespace base{
		namespace internal{
			enum{
				UNIT_SIZE = 32,
				CACHE_COUNT = 4096
			};
#define ROUND_ALIGN(NUM, SIZE) ((NUM%SIZE==0)?NUM:((NUM/SIZE+1)*SIZE))
			static int gs_expand_count = 0;
			inline int ExpandCapcity(int capcity)
			{
				// 尽量是总扩展次数更少,按照128*sizeof(KeyCount)对齐
				gs_expand_count++;
				capcity += capcity < UNIT_SIZE ? UNIT_SIZE : (capcity);
				capcity = ROUND_ALIGN(capcity, InverseSetNew2::ROUND_SIZE);
				return capcity;
			}
			/*
				[内存优化][scofined.qi]
				一次性清理的堆
					最终通过在SpellSearchImpl::BuildIndex中调用InverseSet::Clear()
					将该堆销毁,跳过该堆分配的所有内存的一个个delege[] 阶段
				债券在建立倒排索引阶段,需要建立一个三字符到其所有债券索引数组的映射关系
				AllocArray就是分配对应的预估有ncount个债券索引的债券索引数组
				在倒排索引建立完毕之后(SpellSearchImpl::BuildIndex),所有的债券索引数组内容
				会在m_file.Update(ki.key, ki.ptr);刷新到映射文件中,然后清空内存中的
				IndexIdRange的InverseSet对象(即的m_memory_set不删除,直接设为NULL)
				最终直接销毁对应的堆句柄

				为何需要这么做:
				这些内存是大量的临时内存,临时内存对象与长期内存对象混用内存堆
				会导致内存堆出现大量内存碎片,且导致内存堆的利用率不高
				导致总的内存暴涨短时间内无法降下来
				单独用一个内存堆来管理临时内存,可以非常快速的删除大量内存而且消除内存碎片
			*/
            class OneHeapAllocator {
                void*		m_handle;		// 堆句柄
				int			m_usedsize;		// 已经使用的内存
				int			m_peak_used;	// 使用的峰值
				int			m_alloc_count;
				BaseString	m_name;
			private:
				OneHeapAllocator() = delete;
				OneHeapAllocator(const OneHeapAllocator& heap) = delete;
				OneHeapAllocator& operator=(const OneHeapAllocator& heap) = delete;
			public:
				OneHeapAllocator(const char* name) : m_handle(NULL), m_usedsize(0),
					m_name(name ? name : ""), m_alloc_count(0), m_peak_used(0)
				{
				}
				~OneHeapAllocator(){
					Reset();
				}
				void Reset()
				{
#ifdef WIN32
					if (m_handle != NULL)
					{
						::HeapDestroy(m_handle);
					}
#endif
					m_usedsize = 0;
					m_handle = NULL;
				}
				void* Alloc(int bytes)
				{
					void* ptr = NULL;
#ifdef WIN32
					if (m_handle == NULL)
					{
						m_handle = ::HeapCreate(0, 0, 0);
						if (m_handle)
						{
							BLOGINFO("[MEMORY][HEAP]Heap:%s HeapCreate 0x%8x", m_name.c_str(), m_handle);
						}
					}
					if (m_handle)
					{
						ptr = ::HeapAlloc(m_handle, HEAP_ZERO_MEMORY, bytes);
					}
#else
                    ptr = malloc(bytes);
#endif
					if (ptr == NULL)
					{
						BLOGERR("[MEMORY][HEAP]Heap:%s Alloc %6d failed, m_handle:0x%8x", m_name.c_str(),
							bytes, m_handle);
					}
					else
					{
						m_usedsize += bytes;
						m_peak_used += bytes;
						m_alloc_count++;
					}
					return ptr;
				}

				void Free(void* ptr, int bytes)
				{
                    bool suc = false;
#ifdef WIN32
                    if (m_handle && ptr)
                    {
                        suc = ::HeapFree(m_handle, 0, ptr);
                    }
#else
					free(ptr);
#endif
					if (!suc)
					{
						BLOGERR("[MEMORY][HEAP]Heap:%s Free 0x%8x:%6d failed, m_handle:0x%8x", m_name.c_str(), ptr, bytes, m_handle);
					}
					else
					{
						m_usedsize -= bytes;
						m_alloc_count--;
					}
				}
				int GetBytes()const
				{
					return m_usedsize;
				}
#ifdef WIN32
				void DumpStatus()
				{
					return;
					if (m_alloc_count % 1000 == 0)
						DumpHeapStatus(false);
					else if (m_alloc_count%100==0)
						BLOGDEBUG("[MEMORY][HEAP]heap:%s  0x%8x  used:%8d/%8d count:%d",
						m_name.c_str(), m_handle, m_usedsize,m_peak_used, m_alloc_count);
				}
				void DumpHeapStatus(bool last)
				{
					if (m_handle == NULL)
						return;
					int ncount = 0, ndata = 0, nhead = 0, nholesize = 0, ntotal = 0;
					int ndde = 0, nmove = 0, nregion = 0, nhole = 0;
					if (HeapLock(m_handle))
					{
						PROCESS_HEAP_ENTRY entry = { 0 };
						memset(&entry, 0, sizeof(LPPROCESS_HEAP_ENTRY));
						while (HeapWalk(m_handle, &entry))
						{
							ncount++;
							ntotal += entry.cbData;
							nhead += entry.cbOverhead;
							if (entry.wFlags&PROCESS_HEAP_ENTRY_DDESHARE){
								ndde++; ndata += entry.cbData;
							}
							if (entry.wFlags&PROCESS_HEAP_ENTRY_MOVEABLE){
								nmove++; ndata += entry.cbData;
							}
							if (entry.wFlags&PROCESS_HEAP_REGION)nregion++;
							if (entry.wFlags&PROCESS_HEAP_UNCOMMITTED_RANGE){
								nhole++; nholesize += entry.cbData;
							}
							if (entry.wFlags&PROCESS_HEAP_ENTRY_BUSY &&
								entry.wFlags&PROCESS_HEAP_ENTRY_MOVEABLE)
							{
								BLOGINFO("[MEMORY][HEAP]Block   0x%8x %8d/%8d %8d  ptr:0x%8x",
									entry.lpData, entry.cbData, entry.cbOverhead, entry.iRegionIndex, entry.Block.hMem);
							}
							if (entry.wFlags&PROCESS_HEAP_REGION)
							{
								ndata += entry.Region.dwCommittedSize;
								BLOGINFO("[MEMORY][HEAP]Region  0x%8x %8d/%8d %8d  ptr:0x%8x-0x%8x Commited:%d  UnCommitted:%d total:%d", 
									entry.lpData, entry.cbData, entry.cbOverhead,
									entry.iRegionIndex, entry.Region.lpFirstBlock, entry.Region.lpLastBlock,
									entry.Region.dwCommittedSize, entry.Region.dwUnCommittedSize,entry.cbData);
							}
						}
						HeapUnlock(m_handle);
					}
					BLOGINFO("[MEMORY][HEAP]Heap:%s  HeapDestroy 0x%8x  used:%8d/%8d alloc:%d count:%d data:%d/%d head:%d dde:%d move:%d region:%d hole:%d/%d", 
						m_name.c_str(), m_handle, m_usedsize,m_peak_used, m_alloc_count, ncount, ndata,ntotal, nhead, ndde, nmove, nregion,nhole, nholesize);
				}
#endif
			};
			class KeyCountAllocator : public Singleton<KeyCountAllocator>{
				typedef InverseSet::KeyCount KeyCount;
				typedef HeapAllocator StdAllocator;	// 该分配器已经退化成标准c分配器
				OneHeapAllocator		m_allocator;
			public:
				KeyCountAllocator() :m_allocator("PinyinSearch"){}
				void Reset(){
					m_allocator.Reset();
					BLOGINFO("[MEMORY][PREDICT]扩容次数:%6d", gs_expand_count);
				}
				KeyCount* AllocArray(int ncount)
				{
					return (KeyCount*)m_allocator.Alloc(ncount*sizeof(KeyCount));
				}
				void FreeArray(KeyCount* parray,int capcity)
				{
					//跳过该堆分配的所有内存的一个个delege[] 阶段
					//最终通过Reset来一次性销毁堆,因此不需要一个个释放内存
					//因此这里不需要一个个去释放,当然去释放不会导致问题,只是浪费时间
#ifndef WIN32
					m_allocator.Free(parray, capcity);
#endif
				}
            };
			void InverseSetNew2::Clear()
			{
				KeyCountAllocator::instance()->Reset();
			}
			InverseSetNew2::InverseSetNew2() :m_first(0), m_count(0), m_capcity(0), m_max(1)
			{

			}
			InverseSetNew2::~InverseSetNew2()
			{
				KeyCountAllocator::instance()->FreeArray(m_first, m_capcity);
				m_first = NULL;
			}
			bool InverseSetNew2::add(KeyType key)
			{
				int ipos = find_fast(key,0);
				if (ipos < 0)ipos = find_slow(key,0);
				KeyCount* pid = NULL;
				if (ipos >= 0 && ipos < m_count)
				{
					BASSERT(m_first != NULL);
					pid = m_first + ipos;
					if (pid->getkey() == key)
					{
						BASSERTS(pid->getval() < (1 << kIndexId::CountBits), "计数超限2^%d", kIndexId::CountBits);
						CountType val=pid->addval();
						m_max = m_max < val ? val : m_max;
						return true;
					}
				}
				// 将ipos后面的往后移动一个位置
				if (m_count >= m_capcity || ipos < 0 || m_first == NULL)
				{
					expand();
				}
				BASSERTS(m_first && m_count < m_capcity && m_capcity>0,"");
				ipos = ipos < 0 ? 0 : ipos;
				if (m_count>ipos)
					memmove(&m_first[ipos + 1], &m_first[ipos], (m_count - ipos)*sizeof(KeyCount));
				m_first[ipos] = KeyCount(key, 1);
				m_count++;
				return true;
			}

			void InverseSetNew2::remove(KeyType key)
			{
				int ipos = find(key,0);
				if (ipos < 0 || ipos >= m_count || m_first == NULL)
					return;
				KeyCount& ii = m_first[ipos];
				if (ii.getkey() != key)
					return;
				if (ii.getval() > 1)
				{
					ii.decval();
				}
				else
				{
					// 将后面的向前移动
					for (int i = ipos; i + 1 < m_count; i++)
						m_first[i] = m_first[i + 1];
					m_count--;
					BASSERTS(m_count >= 0, "");
				}
			}
			bool InverseSetNew2::exist(KeyType key) const
			{
				int ipos = find(key,0);
				if (ipos >= 0 && ipos < m_count && m_first)
					return m_first[ipos].getkey() == key;
				return false;
			}

			void InverseSetNew2::intersect(const Base& iis)
			{
				// 取两个集合的并集,忽略CountType
				if (m_count <= 0 || m_first == NULL)
					return;
				int ncount = 0;
				for (int i = 0; i < m_count; i++)
				{
					if (iis.exist(m_first[i].getkey()))
					{
						m_first[ncount++] = m_first[i];
					}
				}
				BASSERTS(ncount <= m_count, "");
				m_count = ncount;
				if (m_capcity > m_count)
					memset(m_first + m_count, 0, (m_capcity - m_count) * sizeof(KeyCount));
			}

			void InverseSetNew2::check(unsigned int maxkey)
			{
				// 调试情况下使用
				if (m_first && m_count > 1)
				{
					KeyCount* last = NULL;
					for (int i = 0; i < m_count; i++)
					{
                    //	BASSERTS(m_first[i].getkey() <= maxkey, "债券索引超限");
                    //	if (last){ BASSERTS(last->getkey() < m_first[i].getkey(), "严格递增检测失败"); }
                    //	BASSERTS(m_first[i].getval() > 0 && m_first[i].getval() <= 254, "计数过大");
						last = m_first + i;
					}
				}
			}
			bool InverseSetNew2::get(int index, KeyType& key, CountType& val) const
			{
				if (index >= 0 && index < m_count && m_first)
				{
					key = m_first[index].getkey();
					val = m_first[index].getval();
					return true;
				}
				key = val = 0;
				return false;
			}
			int InverseSetNew2::find(int key, int npos)const
			{
				int pos = find_fast(key, npos);
				if (pos < 0)pos = find_slow(key, npos);
				return pos;
			}
			int InverseSetNew2::find_fast(KeyType key,int npos) const
			{
				if (npos < 0 || m_first == nullptr || npos >= m_count)
					return m_count;
				if (key <= m_first[npos].getkey())
					return npos;
				if (m_count >= 1)
				{
					KeyType last = m_first[m_count - 1].getkey();
					if (key > last)return m_count;
					if (key == last)return m_count - 1;
				}
				return -1;
			}

			int InverseSetNew2::find(KeyType key, int npos) const
			{
				// 找到key该插入的位置
				// 所有的IndexId是按照key的大小,从小到大,严格递增排序
				int i = find_fast(key,npos);
				if (i < 0)i=find_slow(key,npos);
				if (i >= 0&&i<m_count)
				{
					BASSERTS(i < m_count && m_first[i].getkey() >= key,"i=%d m_count:%d firstkey:%d key:%d",
						i, m_count, m_first[i].getkey(),key);
					BASSERTS(i == 0 || m_first[i - 1].getkey() < key,"");
				}
				return i;
			}
			int InverseSetNew2::find_old(KeyType key, int npos) const
			{
				if (m_first == NULL)
					return -1;
				if (m_count >= 1)
				{
					KeyType last = m_first[m_count - 1].getkey();
					if (key > last)return m_count;
					if (key == last)return m_count - 1;
				}
				if (m_count <= 0 || key <= m_first[0].getkey())
					return 0;
				// 已经废弃
				int left = 0, right = m_count, mid = 0;
				while (left + 4 < right)
				{
					mid = (left + right) >> 1;
					if (key < m_first[mid].getkey())
						right = mid;
					else
						left = mid;
				}

				int i = left;
				for (; i < right; i++)
				{
					if (key <= m_first[i].getkey())
						break;
				}
            //	BASSERTS(i >= 0 && i < m_count, "查找债券索引失败");
            //	if (i - 1 >= 0){ BASSERTS(m_first[i - 1].getkey() < key, ""); }
            //	if (i < m_count){ BASSERTS(key <= m_first[i].getkey(), ""); }
				return i;
			}
			void InverseSetNew2::expand(int cap)
			{
				if (cap > 0 && m_capcity >= cap)
					return;
				if (m_first == NULL || m_count >= m_capcity || m_capcity <= 0)
				{
					int capcity = cap<=0?ExpandCapcity(m_capcity):(max(cap,m_capcity));
					//BLOGDEBUG("[MEMORY]InverseSetNew2 expand %6d ==> %6d  count:%d sizeof(KeyCount):%4d", m_capcity, capcity,
						//m_count, sizeof(KeyCount));
					KeyCount* buf = KeyCountAllocator::instance()->AllocArray(capcity);
					if (m_first)
					{
						if (m_count > 0)
							memcpy(buf, m_first, sizeof(KeyCount)*m_count);
						KeyCountAllocator::instance()->FreeArray(m_first, m_capcity);
					}else
						memset(buf, 0, sizeof(KeyCount)*capcity);
					m_first = buf;
					m_capcity = capcity;
				}
			}
			bool InverseSetNew2::shrink(int delta)
			{
				if (m_first && m_count>0 && m_count + delta < m_capcity)
				{
					KeyCount* buf = KeyCountAllocator::instance()->AllocArray(m_count);
					memcpy(buf, m_first, sizeof(KeyCount)*m_count);
					KeyCountAllocator::instance()->FreeArray(m_first, m_capcity);
					m_first = buf;
					m_capcity = m_count;
					return true;
				}
				return false;
			}
			int InverseSetNew2::find_slow(KeyType k, int npos) const
			{
				if (m_first == nullptr)
					return -1;
				int i = -1;
				int left = npos, right = m_count - 1, mid = 0;
				int key = k;
				int kl, kr, km; int step;
				kl = m_first[left].getkey();
				kr = m_first[right].getkey();
				const int gap = 16;//经过大量测试,16效果最佳
				while (left + gap < right)
				{
					// 二分法:step = (right - left) >> 1;
					// 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
					// 经过测试,真实11w债券数据,比例法性能是二分法的2倍
					step = 1.0*(right - left)*(key - kl) / (kr - kl);
					mid = left + (step < 1 ? gap : step);
					km = m_first[mid].getkey();
					if (key == km){ i = mid; break; }
					if (key < km)
					{
						right = mid;
						kr = m_first[right].getkey();
					}
					else
					{
						left = mid + 1;
						kl = m_first[left].getkey();
					}
				}
				if (i < 0)
				{
					i = left;
					for (; i <= right; i++)
					{
						if (key <= (int)m_first[i].getkey())
							break;
					}
				}
				BASSERT(i < m_count && (int)m_first[i].getkey() >= key);
				BASSERT(i == 0 || (int)m_first[i - 1].getkey() < key);
				return i;
            }



		}//namespace internal
	}//namespace base
}//namespace qb
